package com.fengye.algorithms.leecode.dp;

/**
 * @Author fengye
 * @Date 2023/5/6 19:11
 **/
public class NumberOfLongestIncreasingSubsequence673 {

    public static void main(String[] args) {
        new NumberOfLongestIncreasingSubsequence673().findNumberOfLIS(new int[]{1,3,5,4,7});
    }

    public int findNumberOfLIS(int[] nums) {
        int len = nums.length;
        int max = 0;
        int res = 0;
        int[] dp = new int[len];
        int[] cnt = new int[len];
        for(int i=0;i<len;i++) {
            dp[i] = 1;
            cnt[i] = 1;
            for(int j=0;j<i;j++) {
                if(nums[i] > nums[j]) {
                    if(dp[j]+1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];// 重新计数
                    } else if(dp[j]+1 == dp[i]) {
                        cnt[i] += cnt[j]; // 相等要加前面的次数
                    }
                }
            }
            if(dp[i] > max) {
                max = dp[i];
                res = cnt[i];// 重新计数
            } else {
                res += cnt[i]; // 相等要加前面的次数
            }
        }
        return res;
    }
}
